package leetcode_day._2021._202105._0110;

import general_class.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/5/10 14:45
 * 叶子相似的树
 * 算法：深度优先搜索
 * 直接使用深度优先搜索，把两棵树的叶子节点放到 list 中去
 */
public class _10_872 {

    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> l1 = new ArrayList<>(), l2 = new ArrayList<>();
        dfs(root1, l1);
        dfs(root2, l2);
        if (l1.size() != l2.size()) return false;
        for (int i = 0; i < l1.size(); i++) {
            if (!l1.get(i).equals(l2.get(i))) return false;
        }
        return true;
    }

    public void dfs(TreeNode root, List<Integer> list) {
        if (null == root) return;
        if (null == root.left && null == root.right) {
            list.add(root.val);
            return;
        }
        if (null != root.left) dfs(root.left, list);
        if (null != root.right) dfs(root.right, list);
    }
}
